package com.csx.base.core.algorithm.list;

/**
 * <p> 反转链表:
 * <p> 给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
 * <p> 示例1:
 * <p> 输入：head = [1,2]
 * <p> 输出：[2,1]
 * @author cuisongxu
 * @date 2024/3/2 周六 9:57
 */
public class ReverseList {

    public static void main(String[] args) {

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = null;

        ReverseList reverseList = new ReverseList();
        ListNode listNode = reverseList.reverseList3(node1);
        System.out.println(listNode);
    }


    /**
     * 生成一个新的链表
     * 时间复杂度: O(n)
     * 空间复杂度: O(n)
     *
     */
    public ListNode reverseList(ListNode head) {

        if(head == null || head.next == null) {
            return head;
        }

        ListNode currentNode = null;
        ListNode tempNode = null;
        while(head != null) {

            currentNode = new ListNode(head.val);
            currentNode.next = tempNode;
            head = head.next;
            // 利用临时节点存储当前形成的节点
            tempNode = currentNode;
        }

        return currentNode;
    }


    /**
     * 迭代
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     */
    public ListNode reverseList2(ListNode head) {

        if(head == null || head.next == null) {
            return head;
        }

        ListNode prev = null;
        ListNode curr = head;
        while(curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }



    /**
     * 递归法
     * 时间复杂度: O(n)
     * 空间复杂度: O(n)
     */
    public ListNode reverseList3(ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList3(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }


}
